/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        return validate(root).result
    }

    val FALSE_RESULT = Result(false, null, null)

    // result, min, max
    fun validate(node: TreeNode?): Result {
        if (node == null) return Result(true, null, null)

        val leftResult = validate(node.left)
        val rightResult = validate(node.right)
        if (!leftResult.result) return FALSE_RESULT
        if (!rightResult.result) return FALSE_RESULT

        val leftMax = leftResult.max
        val rightMin = rightResult.min

        if (leftMax != null && leftMax >= node.`val`) return FALSE_RESULT
        if (rightMin != null && rightMin <= node.`val`) return FALSE_RESULT

        return Result(true, leftResult.min ?: node.`val`, rightResult.max ?: node.`val`)
    }

    class Result(val result: Boolean, val min: Int?, val max: Int?)
}

class TreeNode(
    var `val`: Int,
    var left: TreeNode? = null,
    var right: TreeNode? = null
)

println(
    Solution().isValidBST(
        TreeNode(
            `val` = 10,
            left = TreeNode(`val` = 5),
            right = TreeNode(
                `val` = 15,
                left = TreeNode(`val` = 6),
                right = TreeNode(`val` = 20)
            )
        )
    )
)

println(
    Solution().isValidBST(
        TreeNode(
            `val` = 5,
            left = TreeNode(
                `val` = 14,
                left = TreeNode(`val` = 1)
            )
        )
    )
)